package com.ycl.javacore.algorithm;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * LRU缓存：最近最少使用
 */
public class LRUCache {

    /**
     * 定义node节点
     */
    private class Node {
        private int key;
        private int value;
        private Node prev;
        private Node next;

        private Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private int size;
    private int capacity;
    private Map<Integer, Node> map;//存放数据，以便寻找数据的O(1)复杂度
    private Node head;//头尾两个节点是虚拟节点，不存放数据，是为了基于他们增删别的数据节点
    private Node tail;

    /**
     * 定义缓存构造函数和容量
     *
     * @param capacity
     */
    public LRUCache(int capacity) {
        size = 0;
        this.capacity = capacity;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
        map = new HashMap<>();
    }

    /**
     * 获取某个值，如果存在的放到头部
     *
     * @param key
     * @return
     */
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        remove(key);
        addHead(key, node.value);
        return node.value;
    }

    /**
     * 放入某个值，如果存在则更新(先删除，在放到头部)，或者 直接放到头部
     *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            remove(key);
            addHead(key, value);
        } else {
            addHead(key, value);
        }
    }

    /**
     * 添加到头部
     *
     * @param key
     * @param value
     */
    private void addHead(int key, int value) {
        Node newNode = new Node(key, value);
        Node next = head.next;
        newNode.next = next;
        next.prev = newNode;
        head.next = newNode;
        newNode.prev = head;

        size++;
        map.put(key, newNode);

        if (size > capacity) {
            Node prevTail = tail.prev;
            remove(prevTail.key);
        }
    }

    /**
     * 移除某个元素
     *
     * @param key
     */
    private void remove(int key) {
        Node cur = map.get(key);
        Node next = cur.next;
        Node prev = cur.prev;
        prev.next = next;
        next.prev = prev;
        size--;
        map.remove(key);
    }

    /**
     * 按顺序打印节点
     */
    public void printNode() {

        System.out.println("==============");

        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
            if (cur.key != -1) {
                System.out.println("[" + cur.key + "," + cur.value + "]");
            }
        }
    }

    /**
     * 测试结果
     * @param args
     */
    public static void main(String[] args) {

        LRUCache lruCache = new LRUCache(4);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        lruCache.put(4, 4);
        lruCache.printNode();

        lruCache.put(5, 5);
        lruCache.printNode();

        lruCache.get(2);
        lruCache.printNode();

        lruCache.put(6, 6);
        lruCache.printNode();

        lruCache.get(4);
        lruCache.printNode();

    }
}
